Distance entre deux sommets

Définition   Distance entre deux sommets sur un graphe non orienté

Soit  $G$ un graphe non orienté de matrice d’adjacence $A$ . La distance entre deux sommets distincts  $i$ et  $j$ de ce graphe est le plus petit entier  $k$ tel que le terme d’indice  $i,j$ de la matrice  $A^k$ soit non nul.

Remarque

On peut supprimer l’hypothèse  $i$ et  $j$ distincts car, par convention,  $A^0$ est une matrice identité,
donc on trouve une distance nulle entre un sommet et lui-même.